Evaluating the reliability ofMultistate Flow Network (MFN) is an NP-hard problem. Ordered binary decision diagram (OBDD) or\nvariants thereof, such as multivalued decision diagram (MDD), are compact and efficient data structures suitable for dealing with\nlarge-scale problems. Two symbolic algorithms for evaluating the reliability of MFN, MFN OBDD and MFN MDD, are proposed\nin this paper. In the algorithms, several operating functions are defined to prune the generated decision diagrams. Thereby the state\nspace of capacity combinations is further compressed and the operational complexity of the decision diagrams is further reduced.\nMeanwhile, the related theoretical proofs and complexity analysis are carried out. Experimental results show the following: (1)\ncompared to the existing decomposition algorithm, the proposed algorithms take less memory space and fewer loops. (2) The\nnumber of nodes and the number of variables of MDD generated in MFN MDD algorithm are much smaller than those of OBDD\nbuilt in the MFN OBDD algorithm. (3) In two cases with the same number of arcs, the proposed algorithms are more suitable for\ncalculating the reliability of sparse networks.
Loading....